A Parallel Tree code for large Nbody simulation: dynamic load balance and data distribution on CRAY T3D system

摘要

N-body algorithms for long-range unscreened interactions like gravity belongto a class of highly irregular problems whose optimal solution is a challengingtask for present-day massively parallel computers. In this paper we describe astrategy for optimal memory and work distribution which we have applied to ourparallel implementation of the Barnes & Hut (1986) recursive tree scheme on aCray T3D using the CRAFT programming environment. We have performed a series oftests to find an " optimal data distribution " in the T3D memory, and toidentify a strategy for the " Dynamic Load Balance " in order to obtain goodperformances when running large simulations (more than 10 million particles).The results of tests show that the step duration depends on two main factors:the data locality and the T3D network contention. Increasing data locality weare able to minimize the step duration if the closest bodies (directinteraction) tend to be located in the same PE local memory (contiguous blocksubdivison, high granularity), whereas the tree properties have a fine graindistribution. In a very large simulation, due to network contention, anunbalanced load arises. To remedy this we have devised an automatic workredistribution mechanism which provided a good Dynamic Load Balance at theprice of an insignificant overhead.